package Aleehot100;

/**
 * ClassName: c068
 * Package: Aleehot100
 * Description:4. 寻找两个正序数组的中位数
 *
 * @Author BCXJ
 * @Create 2025/8/16 09:48
 * @Version 1.0
 * @Since 1.0
 */
public class c068 {
    public static void main(String[] args) {

    }
    static int nums1LeftMax;
    static int nums1RightMin ;
    static int nums2LeftMax ;
    static int nums2RightMin;
    public static double findMedianSortedArrays(int[] arr1, int[] arr2) {
        // 长度必须区分
        if(arr1.length > arr2.length) {
            return findMedianSortedArrays(arr2, arr1);
        }
        // 长度保存
        int len1 = arr1.length;
        int len2 = arr2.length;
        int total = (len1 + len2 + 1) >> 1;

        int l = 0, r = len1, mid = 0;
        int index1, index2; // arr1 和 arr2 对应的分隔下标
        while(l <= r) {
            index1 = l + ((r - l) >> 1);
            index2 = total - index1;
            nums1LeftMax = (index1 == 0) ? Integer.MIN_VALUE : arr1[index1 - 1];
            nums1RightMin = (index1 == len1) ? Integer.MAX_VALUE : arr1[index1];
            nums2LeftMax = (index2 == 0) ? Integer.MIN_VALUE : arr2[index2 - 1];
            nums2RightMin = (index2 == len2) ? Integer.MAX_VALUE : arr2[index2];
            if((nums1LeftMax <= nums2RightMin) && (nums2LeftMax <= nums1RightMin)) {
                if((len1 + len2) % 2 == 1) {
                    return Math.max(nums1LeftMax, nums2LeftMax);
                } else {
                    return (Math.max(nums1LeftMax, nums2LeftMax) +
                            Math.min(nums1RightMin, nums2RightMin)) / 2.0;
                }
            }
            else if (nums1LeftMax > nums2RightMin) {
                // i 太大，左边元素多了
                r = index1 - 1;
            } else {
                // i 太小，左边元素少了
                l = index1 + 1;
            }
        }
        return 0D;
    }
}
